package my.jwds.p589;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Preorder {

    public static void main(String[] args) {

        Preorder obj = new Preorder();
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public List<Integer> preorder(Node root) {
        if (root == null)return new ArrayList<>();
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        List<Integer> res = new ArrayList<>();
        while(!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            if (node.children != null){
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    stack.push(node.children.get(i));
                }
            }
        }
        return res;
    }
}